// 编写一个程序，通过已填充的空格来解决数独问题。

// 一个数独的解法需遵循如下规则：

// 数字 1-9 在每一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
// 空白格用 '.' 表示。



// 一个数独。



// 答案被标成红色。

// Note:

// 给定的数独序列只包含数字 1-9 和字符 '.' 。
// 你可以假设给定的数独只有唯一解。
// 给定数独永远是 9x9 形式的。

#include <vector>

using namespace std;

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        if (board.empty() || board.size() != 9 || board[0].size() != 9) return;
        DFS(board, 0, 0);
    }
    bool DFS(vector<vector<char>>& board, int i, int j) {
        if (i == 9) return true;
        if (j >= 9) return DFS(board, i+1, 0);
        if (board[i][j] == '.') {
            for (int k = 1; k <= 9; ++k) {
                board[i][j] = (char)(k + '0');
                if (isValid(board, i, j)) {
                    if (DFS(board, i, j+1)) return true;
                }
                    board[i][j] = '.';
            }
        } else {
            return DFS(board, i, j+1);
        }
        return false;
    }
    bool isValid(vector<vector<char>>& board, int i, int j) {
        for (int col = 0; col < 9; ++col) {
            if (col != j && board[i][j] == board[i][col]) return false;
        }
        for (int row = 0; row < 9; ++row) {
            if (row != i && board[i][j] == board[row][j]) return false;
        }
        for (int row = i/3*3; row < i/3*3+3; ++row) {
            for (int col = j/3*3; col < j/3*3 + 3; ++col) {
                if ((row != i || col != j) && board[i][j] == board[row][col]) return false;
            }
        }
        return true;
    }
};

/* 递归，回溯
*/
class Solution {
private:
    // 用一个长度为 9 的布尔类型的数组来记录每个数字是否出现
    bool line[9][9] = {false};     // 9行，line[0][2]==true表示第0行有数字3
    bool column[9][9] = {false};   // 9列
    bool block[3][3][9] = {false}; // 数独块，一共9个
    bool valid{false};
    vector<pair<int, int>> spaces{}; // 空白格的坐标
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int i{0}; i < 9; ++i) {
            for (int j{0}; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j); // 记录空白格坐标
                } else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = true;
                    column[j][digit] = true;
                    block[i/3][j/3][digit] = true;
                }
            }
        }
        dfs(board, 0); // dfs每一个空白格
    }
    void dfs(vector<vector<char>>& board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }
        auto p = spaces[pos];
        int i = p.first;
        int j = p.second;
        for (int digit{0}; digit < 9 && valid != true; ++digit) {
            if (line[i][digit] != true &&
                column[j][digit] != true &&
                block[i/3][j/3][digit] != true)
            {
                line[i][digit] = true;
                column[j][digit] = true;
                block[i/3][j/3][digit] = true;

                board[i][j] = digit + '0' + 1;
                dfs(board, pos + 1);

                // 回溯
                line[i][digit] = false;
                column[j][digit] = false;
                block[i/3][j/3][digit] = false;
            }
        }
    }
};

/* 位运算优化
借助位运算，仅使用一个整数表示每个数字是否出现过
第k位为1，表示数字k+1已经出现过
*/
class Solution {
private:
    int line[9] = {0};
    int column[9] = {0};
    int block[3][3] = {0};
    bool valid{false};
    vector<pair<int, int>> spaces{};
public:
    void solveSudoku(vector<vector<char>>& board) {
        for (int i{0}; i < 9; ++i) {
            for (int j{0}; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                } else {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }
        dfs(board, 0);
    }
    void flip(int i, int j, int digit) {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i/3][j/3] ^= (1 << digit);
    }
    void dfs(vector<vector<char>>& board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }
        auto p = spaces[pos];
        int i = p.first;
        int j = p.second;
        int mask = ~(line[i] | column[j] | block[i/3][j/3]) & 0x1ff;
        // b 和最低位的 1 进行按位异或运算，就可以将其从 b 中去除，这样就可以枚举下一个 1
        for (; mask != 0 && valid != true; mask &= (mask - 1)) {
            int digitMask = mask & (-mask); // b & (−b) 得到 b 二进制表示中最低位的 1
            int digit = __builtin_ctz(digitMask); // 返回二进制下末尾的0的个数
            flip(i, j, digit);
            board[i][j] = digit + '0' + 1;
            dfs(board, pos + 1);
            flip(i, j, digit);
        }
    }
};

/* 枚举优化
我们可以顺着方法二的思路继续优化下去：
如果一个空白格只有唯一的数可以填入，也就是其对应的 b 值和 b−1 进行
按位与运算后得到 0（即 b 中只有一个二进制位为 1）。
此时，我们就可以确定这个空白格填入的数，而不用等到递归时再去处理它。
这样一来，我们可以不断地对整个数独进行遍历，将可以唯一确定的空白格全部填入对应的数。
随后我们再使用与方法二相同的方法对剩余无法唯一确定的空白格进行递归 + 回溯。
*/
class Solution {
private:
    int line[9];
    int column[9];
    int block[3][3];
    bool valid;
    vector<pair<int, int>> spaces;

public:
    void flip(int i, int j, int digit) {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3][j / 3] ^= (1 << digit);
    }

    void dfs(vector<vector<char>>& board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }

        auto [i, j] = spaces[pos];
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        for (; mask && !valid; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            int digit = __builtin_ctz(digitMask);
            flip(i, j, digit);
            board[i][j] = digit + '0' + 1;
            dfs(board, pos + 1);
            flip(i, j, digit);
        }
    }

    void solveSudoku(vector<vector<char>>& board) {
        memset(line, 0, sizeof(line));
        memset(column, 0, sizeof(column));
        memset(block, 0, sizeof(block));
        valid = false;

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }

        while (true) {
            int modified = false;
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                        if (!(mask & (mask - 1))) {
                            int digit = __builtin_ctz(mask);
                            flip(i, j, digit);
                            board[i][j] = digit + '0' + 1;
                            modified = true;
                        }
                    }
                }
            }
            if (!modified) {
                break;
            }
        }

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                }
            }
        }

        dfs(board, 0);
    }
};